"""
给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
    3
   / \
  9  20
    /  \
   15   7
"""

class Solution:
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def maxDeep(r):
            if not r: return 0
            left = maxDeep(r.left)
            right = maxDeep(r.right)
            return max(left, right) + 1

        def isBalance(r):
            if not r: return True
            left = maxDeep(r.left)
            right = maxDeep(r.right)
            if abs(left-right) > 1: return False
            return isBalance(r.left) and isBalance(r.right)
        return isBalance(root)